A portion of this disclosure may contain copyrighted material. The copyright owner has no objection to the facsimile reproduction by anyone of the patent document or the patent disclosure, as it appears in the Patent and Trademark Office patent file or records, but otherwise reserves all copyright rights.
The present invention relates generally to geometric modeling using polygonal meshes for computer graphics, and more particularly relates to techniques for optimizing computer resource (e.g., memory, CPU, etc.) requirements for the manipulation of large-scale meshes.
Rendering real-time views on a complex model is a computation-intensive task. Current methods generally rely on encoding real-world objects in a complex three-dimensional geometric model which approximates the surfaces, textures and locations of the real-world objects. Objects are usually represented as a collection of polygons (but can be a mathematical description, fractal or the like) which are collected together to form a mesh having the shape and visual and/or tactile characteristics of the encoded real-world object. Realistic models of any reasonable size, e.g., simulating large-scale terrain meshes (see FIG. 2), can contain hundreds of meshes with millions of polygons to represent a realistic view of reality. Consequently, enormous computer resources are required to manipulate large meshes.
To simplify processing when rendering views of such detailed scenes, view-dependent progressive-meshes (VDPM) were developed. Hoppe shows a VDPM framework that represents an arbitrary delta-mesh (base mesh plus deltas required to produce a more detailed mesh)as a hierarchy of geometrically optimized transformations. A series of geomorph operations can be performed to convert between differing levels of detail of the progressive mesh. (For further information, see Hoppe, Progressive Meshes, Computer Graphics Proceedings, Annual Conference Series (ACM SIGGRAPH), pp. 99-108 (1996); Hoppe, View-Dependent Refinement of Progressive Meshes, ACM SIGGRAPH, pp. 189-198 (1997).)
In accordance with Hoppe""s VDPM framework, a front across a progressive mesh hierarchy is defined. The Hoppe VDPM framework uses a progressive mesh representation of the original mesh model, which represents the mesh model as a simplified base mesh and a sequence of mesh refinement transformations (i.e., vertex splits) that, when applied to the base mesh, exactly reconstruct the original fully-detailed mesh. The front is developed by incrementally applying mesh refinement and coarsening operations subject to certain legality considerations. The legality conditions disallow some refinement operations unless other refinements operations are performed, and disallow some coarsening operations unless other coarsening operations are performed first
In addition, for a given mesh, a viewpoint is defined with respect to the mesh. The viewpoint can correspond to what a user/viewer might see of a mesh, or it can be the portions of the mesh visible in a viewport. The phrase xe2x80x9cselectively refined meshxe2x80x9d (SRM) corresponds to a mesh that is altered based on satisfying certain viewing criteria, such as changes in the viewport. The result is view-dependent level of detail (LOD) applied to different portions of a mesh. For example, viewing conditions may depend on the location of a flight simulator pilot in a mesh model, so that mesh detail centers on those portions of the mesh near the pilot""s plane. For a view-dependent LOD, the active front is traversed for each frame being rendered, and every vertex of the front is either coarsened or refined based on the view-dependent refinement criteria. Examples of view-dependent criteria affecting the occurrence of a vsplit (vertex split) operation is whether a vertex""s neighborhood intersects the view frustum (see FIG. 7), has a Gauss map not strictly oriented away, or has a screen-projected deviation from M that exceeds a pre-determined (user-specified) pixel tolerance. (M represents an original fully-detailed mesh that has been deconstructed into a base mesh, to which delta operations are applied to obtain successively detailed meshes.)
It is understood by those skilled in the art that view dependencies concern the relationship between a viewpoint (e.g., camera location, user""s eye, etc.), a defined viewing frustum (see FIG. 7), and a xe2x80x9ccurrent meshxe2x80x9d defined by a base mesh M0+a set of refinement operations. When adjusting a SRM""s coarseness, the change is either effected instantly, or geomorphed (interpolated) over time. Which method is used depends on whether an affected mesh region is entering, leaving, or staying within a particular viewing frustum. Only portions of a mesh remaining in view (i.e., within the frustum) need to be geomorphed to avoid xe2x80x9cpoppingxe2x80x9d the mesh alteration into place. In fact, geomorphs should be avoided for vertices entering and leaving the frustum, as discussed later.
Preferably, vertices entering and leaving the frustum are instantly adjusted, and vertices remaining in view are geomorphed over time. In addition, polygon orientation and distance from the frustum can be used to determine whether a local region of the mesh should be further refined or coarsened. For example, those polygons identified as facing away from a viewing position, or having too little impact on the display device, can be ignored without affecting output. The impact of a triangle""s rendering to an output device (e.g., display monitor or video output) is dependent on the resolution of the device; if rendering only changes one or two pixels on the output device, rendering the triangle may cost more in computer time and resources than the visual benefit obtained from the rendering.
In addition, another significant problem with prior art mesh-based rendering systems is that notwithstanding using simplified meshes, these systems consume computer resources proportional to the size of the fully-detailed mesh Mn. That is, in the prior art, if Mn has p faces, but has been simplified into a simpler mesh M0 having only q faces, where q less than  less than p (much less than), memory and other computer resources are allocated on a scale proportional with the connectivity of the larger mesh Mn. For example, to compute a geomorph between two selectively refined meshes procured from the progressive mesh hierarchy, prior art methods may require geomorph computations involving all active vertices, rather than on just those vertices needed for a view-dependent computation. And, once begun, the geomorph had to complete (or be reverted) before a new geomorph operation can be initiated. Consequently, computer resources (e.g. CPU speed, time, and storage space) to store and process the fully-detailed mesh are required even though the view is rendered based on only a small subset of its vertices.
For further information regarding techniques for constructing and using progressive meshes, view-dependent progressive meshes, and geomorphs, see: U.S. Patent AA for Encoding And Progressive Transmitting Of Progressive Meshes, bearing application Ser. No. 08/586,953 and filed Jan. 11, 1996; U.S. Patent BB for Selective Refinement Of Progressive Meshes, bearing application Ser. No. 08/797,501 and filed Feb. 7, 1997; U.S. Patent CC for View-Dependent Refinement Of Progressive Meshes, bearing application Ser. No. 08/826,570 and filed Apr. 3, 1997; U.S. Patent DD for Adaptive Refinement Of Progressive Meshes, bearing application Ser. No. 08/826,573 and filed Apr. 3, 1997; and U.S. Patent EE for a Method For Creating Progressive Simplicial Complexes, bearing application Ser. No. 08/880,090 and filed Jun. 20, 1997. These patents are incorporated herein by reference.
To overcome these limitations of prior art systems, the invention optimizes storage requirements by utilizing dynamic data structures for storing and manipulating a mesh that allocate storage based on the active vertices of the mesh (determined according to view-dependent criteria). This contrasts the prior art teachings of using static data structures proportional to the fully-detailed mesh. So, instead of statically storing mesh connectivity for an entire fully-detailed mesh Mn (prior art), static data structures only encode the vertex hierarchy of the simplest mesh M0 and the refinement dependencies required to produce Mn. Separate dynamic data structures encode, according to changes in view-dependent parameters, vertices and morph states for an active mesh. This results in substantial resource savings when (as is typical) the fully-detailed mesh is large, but the number of active vertices is just a small subset of the overall number of vertices.
The invention optimizes resource usage (e.g. storage and processor) by imperceptibly spreading transaction costs across multiple stages. Thus, for example, when performing a view-dependent selective refinement operation, rather than computing refinements for all active vertices in every frame, instead only a subset of the vertices might be considered in a given time period (or frame range). And, of those vertices determined to require alteration by geomorph or otherwise, only a subset of those vertices might be altered in a given time period.
Preferably, each stage is selected such that the multi-stage process is imperceptible to a viewer. For example, assume it is not noticeable if vertex evaluation is staged across xc2xd second of video. If the frame rate is 30 frames per second (fps), then the vertex evaluation can be spread across 15 frames, say one third processed each 5 frames. For each stage, a vertex can be determined as requiring refinement or coarsening. In this fashion, the invention can tailor rendering to the available resources of a host computing environment.
As a further optimization, when performing refinement operations, one of the new vertices from a vertex split (vsplit) operation can be required to assume the position of the ancestor vertex. This then ensures that only one new vertex need be allocated in the mesh data structures at every split.
As a further optimization, if it is determined that a geomorph refinement is required, a time limit can also be set for applying the geomorph. In effect this is the inverse of multi-staging the vertex evaluations. That is, in the former, a maximum number of frames is determined (e.g., 15), and the evaluation process distributed across them. Here, a maximum time limit for the geomorph is selected, and this determines the size of the incremental step taken in each video frame. For example, a geomorph can be set to occur over a one second period, so that the number of interpolation steps equals the frame rate fr (e.g., 60 frames/sec=60 transition steps, each having duration frxe2x88x921). And, as with multi-stage vertex evaluations, one can also distribute geomorphs across multiple stages.
As a further enhancement over the prior art, geomorphs are overlapped to more efficiently process them. Geomorphing means, by definition, a mesh alteration that is being spread over time. A common problem is that a rapid change in viewing perspective can cause the end result of an in-progress geomorph to become invalid before it has completed. With prior art systems, before the new geomorph can be applied, the ongoing geomorph has to be completed normally, instantly xe2x80x9cpoppedxe2x80x9d to completion, or reverted. In each case, either time is wasted or visual artifacts introduced into the rendered output. To overcome these limitations, illustrated embodiments allow a geomorph to be altered mid-morph.
For example, assume an ongoing geomorph between first and second selectively refined meshes, SRM1 and SRM2. For these two SRM paths, a geomorph g(1) is constructed at run-time having all the lowest level vertices from both SRM paths through the refinement hierarchy. Vertices from active mesh SRM1 then start gravitating towards SRM2. Vertices from g(1) supply required ancestors/descendants for moving between SRM1 and SRM2. Now assume the viewpoint changes because a simulator combat-pilot maneuvers her plane to avoid being destroyed. This results in a SRM3. Currently-morphing vertices will now gravitate towards the new requested SRM3. When one introduces a new SRM3 path across the hierarchy, this results in a new geomorph g(2) corresponding to the vertex states from g(1) and SRM2. Intermediate vertices, which are at some interpolated position between SRM1 and SRM2, stop gravitating towards SRM2 and instead begin gravitating towards SRM3. By calculating these geomorph operations at run-time, it is no longer necessary to compute geomorphs between entire mesh levels (i.e. for all active vertices).
When a geomorph is interrupted with a new geomorph, in some embodiments, the motion of the vertex will simply stop progress on the original path, and will instead begin to move towards the new destination. In other embodiments, the path of the interrupted vertex follow a spline path having the original interrupted destination as a control point along a path terminating with the new destination. These intermediate control points can be stacked as new destinations interrupt the geomorph in progress.
Additional features and advantages of the invention will be made apparent from the following detailed description of an illustrated embodiment which proceeds with reference to the accompanying drawings.